#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;

#define ERROR 0x3f3f

bool is_legel(string infix)
{
//-1变0-1，‘-’前面的不是数字？？？-1？？，就变成？？？（0-1）
//括号对不上，有左括号无右括号，左括号数量>右括号, 反之则右括号>左括号
//符号重复,如'*/','(/)', 就是当两个符号连在一起时,除非①右边有'(',②左边有')'---则判定为违法
//一个小数中有两个'.',放到之后判定数字中
//除数为0，放到之后计算中
//有非法字符,其中将' '去掉,全角字符转半角
	int i = 0;
	int left_num = 0;
	int right_num = 0;
	while (i < infix.length()) 
    {
		if (i == 0 && (isdigit(infix[i]) || infix[i]=='(' || infix[i]=='-') == false )
		{	
			cout << "开头出现符号逻辑错误" << endl;
			return false;
		}

		if (infix[i] == '+' ||infix[i]== '-' ||infix[i]== '*' ||infix[i]== '/' || infix[i]=='(' ||infix[i]== ')' ||infix[i]== '^' || infix[i]=='.' || isdigit(infix[i]))
		{

		}  //不是运算符+不是数字
		else
		{
			cout << "出现非法字符" << endl;
			return false;
		}

		if (infix[i] == '+' || infix[i] =='-' || infix[i] =='*' || infix[i] =='/'  || infix[i] =='^')
		{
			if(infix[i+1] =='*' || infix[i+1] =='/'  || infix[i+1] =='^' || infix[i+1] =='.')
			{
				cout << "运算符之后还是运算符或是小数点" << endl;
				
			}
			if(infix[i+1] == '-' && (i+2) < infix.length())
			{
				if (isdigit(infix[i+2])== false)
				{
					cout << "负号后面不应接着符号" << endl;
					return false;
				}
			}
		}
		if (infix[i] == '.')
		{
			if (isdigit(infix[i+1]) == false)
			{
				cout << "小数点后不应出现符号" << endl;
				return false;
			}
		}

		if (infix[i] == ')')
		{
			if (infix[i+1] == '(')
			{
				cout << "符号出现逻辑错误" << endl;
				return false;
			}
		}


		if (infix[i] == '(') left_num+=1;
		if (infix[i] == ')') right_num+=1;
		if (left_num < right_num)
		{
			cout << "左右括号数不一致" << endl;
			return false;
		}
		if (i == infix.length()-1 && ((isdigit(infix[i]) || infix[i]==')') == false) )
		{
			cout << "结尾出现符号逻辑错误" << endl;
			return false;
		}
		i++;
	}
	if (left_num != right_num)
	{
		cout << "左右括号数不一致" << endl;
		return false;
	}
	return true;

}
/**
 * char转化为string输出
*/
string cto_string(char c) {
	stringstream stream;
	stream << c;
	return stream.str();
}

/***
 * 优先级判断:
 * 优先级a>b为1;a=b为0;a<b为-1
 * 
*/
int cmp(char a, char b) 
{
	if (a=='+') 
	{
		if (b == '-' || b == '+') 
			return 0;
		else if (b == '*' || b == '/' || b == '^' ) 
			return -1;
		else if (b == '(') 
			return 1; 
	} 
	else if (a == '-') 
	{
		if (b == '-' || b == '+') 
			return 0;
		else if (b == '*' || b == '/' || b == '^') 
			return -1;
		else if (b == '(') 
			return 1; 
	} 
	else if (a == '*')
	 {
		if (b == '*' || b == '/')
			return 0;
		else if(b == '+' || b == '-' || b == '(') 
			return 1;
		else if(b == '^')
			return -1;
	}
	else if (a == '/') 
	 {
		if (b == '*' || b == '/') 
			return 0;
		else if(b == '+' || b == '-' || b == '(') 
			return 1;
		else if(b == '^')
			return -1;
	} 
	else if (a == '^')
	{
			return 1;
	}
	return 0;
} 

/***
 * 定义除法,方便之后抛出异常
*/
double division(double a, double b)
{
   if( b == 0 )
   {
      throw "除数不能为0!";
   }
   return (a/b);
}

/**
 * 计算后缀表达式的值 
 * 
 * */
double caculate(vector<string>& a) {
    stack<double> st;
    for (auto x : a) 
    {
        if (x == "+") 
        {
            double a = st.top();st.pop();
            double b = st.top();st.pop();
            st.push(b + a);
        }
        else if (x == "-") 
        {
            double a = st.top();st.pop();
            double b = st.top();st.pop();
        	st.push(b - a);
        }
        else if (x == "*") 
        {
            double a = st.top();st.pop();
            double b = st.top();st.pop();
            st.push(b * a);
        }
        else if (x == "/") 
        {
            double a = st.top();st.pop();
            double b = st.top();st.pop();
			try 
			{
				st.push(division(b, a));
			}
			catch (const char* msg) 
			{
				cerr << msg << endl;
			}//考虑除数为0的问题
        }
		else if (x == "^") 
        {
            double a = st.top();st.pop();
            double b = st.top();st.pop();
            st.push(pow(b,a));
        } 
        else
        {
            st.push(stof(x));
        }
            
	}
    return st.top();
}

/***
 * 中缀表达式转后缀表达式
*/
int caculator(string infix) 
{
    vector<string> res;
	if(is_legel(infix) == false)
	{
		return 0;
	}
	stack<char> st;
	int i = 0;
	bool is_nagative = false;
	while (i < infix.length()) 
    {
		if (infix[i] == '(') 
        {
			st.push(infix[i]);
			i++;
		} 
        else if (infix[i] == ')') 
        {
			i++;
			while (!st.empty()) 
            {
				char op = st.top();st.pop();
				if (op == '(') 
                    break;
				else 
                    res.push_back(cto_string(op));
			}
		} 
        else if (isdigit(infix[i])) 
        {
			double n = infix[i] - '0';
			double f = 0;
			double point = 0.1;
			i++;
			bool is_double = false;
			int point_num = 0;
			
			while (i < infix.length() && isdigit(infix[i]) || infix[i]=='.')
            {
				if(infix[i] != '.' && is_double == false)
				{
					n = n * 10 + (infix[i] - '0'); 
					i++;
				}
				else if (infix[i] == '.')  //合法性检验,如果出现两个'.',则不合法
				{
					f = point*(infix[++i] - '0');
					point = 0.1*point;
					is_double = true;	
					i++;
					point_num +=1;
					if (point_num > 1)
					{
						cout << "出现两个'.'" << endl;
						return 0;
					}
				}
				else
				{
					f+=point*(infix[i]-'0');
					point = 0.1*point;
					i++;
				}
				
			}

			ostringstream oss;  //将double转化成string并去掉末尾的0
			if (is_nagative)  //是不是负数
			{
				oss<<(-(n+f));
				is_nagative = false;
			}
			else
			{
				oss<<(n+f);
			}

			res.push_back(oss.str());
		} 
		else if (infix[i] == '-' && isdigit(infix[i-1]) == false && isdigit(infix[i+1])== true)
		{
			//鉴定为负数
			is_nagative = true;
			i++;
		}
        else 
		{
			if (st.empty()) 
                st.push(infix[i]);
			else 
            {
				if (cmp(infix[i], st.top()) > 0) 
                    st.push(infix[i]);
				else if (cmp(infix[i], st.top()) <= 0) 
                {
					while (!st.empty()) 
                    {
						char op = st.top();st.pop();
						if (op == '(')
						{
							st.push(op);
						}
						else
						{
							res.push_back(cto_string(op));
						}
						if (!st.empty())
						{
							if (cmp(infix[i], st.top()) > 0) break;
						}
					}
					st.push(infix[i]); 
				}
			}
			i++;
		}
	}
	while (!st.empty()) 
    {
		res.push_back(cto_string(st.top())); st.pop();
	}

	cout <<"|" << infix << "    |";
	for (string i:res) cout<<i<<" ";
	double ans;
	ans = caculate(res);
    cout << "| " << ans <<  "|"  << endl;
	return 0;
} 


